package com.cn.codebrush.排序;

/**
 * @Author Boolean
 * @Date 2022/5/29 16:03
 * @Version 1.0
 */
public class 快速排序 {
    public static void main(String[] args) {
        int[] nums = {2,4,6,7,1,3,9,8,5};
        nums = quick(nums,0,nums.length-1);
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]);
        }

    }

    //int[] nums = {4,2,6,7,1,3,9,8,5};
    //  temp = 4
    //  326713985   low=1,high=5
    //  326716985   low=2,high=5
    //  324716985   low=2,high=5
    //  321716985   low=2,high=4
    //  321476985   low=3,high=3
    public static int[] quick(int[] nums,int low,int high){
        if(low < high){
            int index = quickHelper(nums,low,high);
            quick(nums,low,index-1);
            quick(nums,index+1,high);
        }
        return nums;
    }

    public static int quickHelper(int[] nums,int low,int high){
        int temp = nums[low];
        while(low < high){
            while (low < high && nums[high] >= temp){
                high--;
            }
            nums[low] = nums[high];

            while (low < high && nums[low] <= temp){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = temp;
        return low;
    }


}
